/*
 * @Author: szx
 * @Date: 2022-04-27 13:40:41
 * @LastEditTime: 2022-04-27 14:01:48
 * @Description:
 * @FilePath: \leetcode\400-499\417\417.js
 */
/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    const m = heights.length;
    const n = heights[0].length;
    const pacific = new Array(m).fill(false).map(() => new Array(n).fill(false));
    const atlantic = new Array(m).fill(false).map(() => new Array(n).fill(false));
    const dfs = (row, col, ocean) => {
        if (ocean[row][col]) return;
        ocean[row][col] = true;
        for (const dir of dirs) {
            const newRow = row + dir[0],
                newCol = col + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
                dfs(newRow, newCol, ocean);
            }
        }
    };
    for (let i = 0; i < m; i++) {
        dfs(i, 0, pacific);
        dfs(i, n - 1, atlantic);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j, pacific);
        dfs(m - 1, j, atlantic);
    }
    const res = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pacific[i][j] && atlantic[i][j]) {
                res.push([i, j]);
            }
        }
    }
    return res;
};
